#include <algorithm>
#include <iostream>
#include <string>

#include "ezstl_allocator.hpp"
#include "ezstl_deque.hpp"
#include "ezstl_hash_fun.hpp"
#include "ezstl_hashmap.hpp"
#include "ezstl_hashset.hpp"
#include "ezstl_hashtable.hpp"
#include "ezstl_heap.hpp"
#include "ezstl_list.hpp"
#include "ezstl_queue.hpp"
#include "ezstl_stack.hpp"
#include "ezstl_vector.hpp"

void TestVector() {
  using namespace ezstl;
  Vector<std::string> vec(5, "0");
  Vector<std::string> vec2(vec.begin(), vec.end());
  Vector<std::string> vec3{vec};

  vec.show();
  vec2.show();
  vec3.show();
  std::cout << "===============\n";
  Vector<std::string> vec4(std::move(vec));
  vec4.show();
  vec.show();
  std::cout << "===============\n";
  vec.swap(vec4);
  vec4.show();
  vec.show();
  std::cout << "===============\n";
  vec.reserve(8);
  vec.show();
  std::cout << "===============\n";
  Vector<std::string> vec5(7, "9");
  Vector<std::string> tmp(5, "8");

  vec5.show();
  vec5 = tmp;
  vec5.show();

  std::cout << "===============\n";
  Vector<std::string> vec6{6, "6"};
  vec6.show();
  tmp.show();
  vec6 = std::move(tmp);
  vec6.show();
  tmp.show();
  std::cout << "===============\n";
  vec6.clear();
  vec6.show();
  std::cout << "===============\n";
  Vector<std::string> vec7{10, "7"};
  vec7.reserve(20);
  // elems_after > count
  // vec7.insert(vec7.begin() + 2, 2, "3");
  // elems_after < count
  vec7.insert(vec7.begin() + 7, 5, "3");
  vec7.show();
  std::cout << "===============\n";
  vec7.insert(vec7.begin(), "1");
  vec7.show();
  vec7.insert(vec7.end(), "10");
  vec7.show();
  std::cout << "===============\n";
  vec7.erase(vec7.begin());
  vec7.show();
  vec7.erase(vec7.begin() + 7, vec7.begin() + 12);
  vec7.show();
  std::cout << "===============\n";
  vec7.push_back("123");
  vec7.emplace(vec7.end(), "1234");
  vec7.show();
  std::cout << "===============\n";
  vec7.resize(10);
  vec7.show();
  vec7.resize(15, "12");
  vec7.show();
  vec7.resize(25, "123");
  vec7.push_back("test");
  vec7.show();
  std::cout << "===============\n";
  vec7.pop_back();
  vec7.show();
  std::cout << "===============\n";
}
#if 1
void TestList() {
  using namespace ezstl;
  using list = List<std::string>;

  list list1;
  for (int i = 0; i < 5; i++) {
    list1.insert(list1.begin(), std::to_string(i));
    list1.insert(list1.end(), std::to_string(i));
  }
  list1.insert(++list1.begin(), "12");
  list1.show();
  auto it = list1.insert(list1.end(), 5, "10");
  list1.show();
  std::cout << *(--it) << std::endl;
  std::cout << list1.front() << std::endl;
  std::cout << list1.back() << std::endl;
  list1.erase(list1.begin());
  list1.show();
  list1.erase(++list1.begin(), --list1.end());
  list1.show();
  std::cout << list1.size() << std::endl;
  std::cout << "========================\n";
  list l2;
  for (int i = 0; i < 5; i++) {
    l2.insert(l2.begin(), "12");
  }
  std::cout << l2.size() << std::endl;
  std::cout << *l2.begin() << std::endl;
  std::cout << l2.begin()->size() << std::endl;
  std::cout << "========================\n";
  list list3{l2};
  list3.show();
  list list4{4};
  list4.show();
  list list5{5, "10"};
  list5.show();
  std::cout << "========================\n";
  list5.resize(3);
  list5.show();
  std::cout << "========================\n";
  list5.merge(list3);
  list3.show();
  list5.show();
  std::cout << "========================\n";
  list list6{6, "13"};
  list6.show();
  list5.show();
  list6.splice(list6.begin(), list5, list5.begin());
  list5.show();
  list6.show();
  std::cout << "========================\n";
  list6.reverse();
  list6.show();
  std::cout << "========================\n";
  list6.insert(list6.end(), 2, "5");
  list6.show();
  list6.sort();
  list6.show();
}
#endif

void TestDeque() {
#if 1
  using deque = ezstl::Deque<std::string>;
  {
    std::cout << "========================\n";
    deque dq1{5, "6"};
    dq1.show();
    std::cout << "========================\n";
  }
  {
    std::cout << "========================\n";
    ezstl::Deque<int> dq2{};
    for (int i = 0; i < 10; i++) {
      dq2.push_back(i);
    }
    dq2.show();
    for (int i = 10; i < 20; i++) {
      dq2.push_front(i);
    }
    dq2.show();
    std::cout << "========================\n";
    auto it = std::find(dq2.begin(), dq2.end(), 11);
    std::cout << *it << std::endl;
    std::cout << *(it.cur) << std::endl;
    std::cout << "========================\n";
    dq2.show();
    for (int i = 0; i < 5; i++) dq2.pop_back();
    dq2.show();
    for (int i = 0; i < 5; i++) dq2.pop_front();
    dq2.show();
    std::cout << "========================\n";
  }
  {
    std::cout << "========================\n";
    ezstl::Deque<int> dq3;
    for (int i = 0; i < 500; i++) dq3.push_back(i);
    // dq3.show();
    dq3.clear();
    // dq3.show();
    std::cout << "========================\n";
  }
  {
    std::cout << "========================\n";
    ezstl::Deque<std::string> dq4;
    for (int i = 0; i < 10; i++) dq4.push_back("1");
    dq4.show();
    {
      auto ret = dq4.insert(dq4.begin(), 15, "12");
    }
    dq4.show();
    {
      auto ret = dq4.insert(dq4.end(), 15, "13");
      std::cout << *(ret - 1) << " " << *ret << std::endl;
    }
    dq4.show();
    std::cout << "========================\n";
  }
  {
    std::cout << "========================\n";
    ezstl::Deque<std::string> dq5;
    for (int i = 0; i < 10; i++) dq5.push_back(std::to_string(i));
    dq5.show();
    std::cout << *(dq5.begin() + 4) << std::endl;
    {
      auto ret = dq5.insert(dq5.begin() + 4, 5, "12");
      std::cout << *(ret - 1) << " " << *ret << std::endl;
    }
    dq5.show();
    {
      auto ret = dq5.insert(dq5.end() - 2, 5, "13");
      std::cout << *(ret - 1) << " " << *ret << std::endl;
    }
    dq5.show();
    std::cout << "========================\n";
  }
#endif

#if 1
  {
    std::cout << "========================\n";
    ezstl::Deque<std::string> dq6;
    for (int i = 0; i < 79; i++) dq6.push_back(std::to_string(i));
    std::cout << "========================\n";
  }
#endif
  {
    std::cout << "========================\n";
    int a[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    ezstl::Deque<int> dq7{a, a + 9};
    dq7.show();
    std::cout << "========================\n";
  }
}

void TestStack() {
  using namespace ezstl;
  Stack<int> stk;
  for (int i = 0; i < 10; i++) stk.push(i);
  while (!stk.empty()) {
    std::cout << stk.top() << std::endl;
    stk.pop();
  }
  std::cout << "========================\n";
  Stack<std::string> stk2;
  for (int i = 0; i < 5; i++) stk2.push("123123");
  while (!stk2.empty()) {
    std::cout << stk2.top() << std::endl;
    stk2.pop();
  }
  std::cout << "========================\n";
  Stack<int, List<int>> stk3;
  for (int i = 0; i < 5; i++) stk3.push(i);
  while (!stk3.empty()) {
    std::cout << stk3.top() << std::endl;
    stk3.pop();
  }
}

void TestQueue() {
  using namespace ezstl;
  Queue<int> q;
  for (int i = 0; i < 10; i++) q.push(i);
  while (!q.empty()) {
    std::cout << q.front() << " ";
    q.pop();
  }
  std::cout << std::endl;
  std::cout << "========================\n";
  Queue<std::string> q2;
  for (int i = 0; i < 5; i++) q2.push("123123");
  while (!q2.empty()) {
    std::cout << q2.front() << " ";
    q2.pop();
  }
  std::cout << std::endl;
  std::cout << "========================\n";
  Queue<int, List<int>> q3;
  for (int i = 0; i < 5; i++) q3.push(i);
  while (!q3.empty()) {
    std::cout << q3.front() << " ";
    q3.pop();
  }
}

void TestHeapOption() {
  {
    using namespace ezstl::heap_detail;
    int a[9] = {0, 1, 2, 3, 4, 8, 9, 3, 5};
    ezstl::Vector<int> ivec{a, a + 9};
    ezstl::make_heap(ivec.begin(), ivec.end());
    for (auto& i : ivec) std::cout << i << " ";  // 9 5 8 3 4 0 2 3 1
    std::cout << std::endl;

    ivec.push_back(7);
    ezstl::push_heap(ivec.begin(), ivec.end());
    for (auto& i : ivec) std::cout << i << " ";  // 9 7 8 3 5 0 2 3 1 4
    std::cout << std::endl;

    ezstl::pop_heap(ivec.begin(), ivec.end());
    std::cout << ivec.back() << std::endl;  // 9
    ivec.pop_back();

    for (auto& i : ivec) std::cout << i << " ";  // 8 7 4 3 5 0 2 3 1
    std::cout << std::endl;

    ezstl::sort_heap(ivec.begin(), ivec.end());
    for (auto& i : ivec) std::cout << i << " ";
    std::cout << std::endl;
  }
  std::cout << "========================\n";
  {
    using namespace ezstl::heap_detail;
    std::string a[9] = {"0", "1", "2", "3", "4", "8", "9", "3", "5"};
    ezstl::Vector<std::string> ivec{a, a + 9};
    ezstl::make_heap(ivec.begin(), ivec.end());
    for (auto& i : ivec) std::cout << i << " ";
    std::cout << std::endl;

    ivec.push_back("7");
    ezstl::push_heap(ivec.begin(), ivec.end());
    for (auto& i : ivec) std::cout << i << " ";
    std::cout << std::endl;

    ezstl::pop_heap(ivec.begin(), ivec.end());
    std::cout << ivec.back() << std::endl;
    ivec.pop_back();

    for (auto& i : ivec) std::cout << i << " ";
    std::cout << std::endl;

    ezstl::sort_heap(ivec.begin(), ivec.end());
    for (auto& i : ivec) std::cout << i << " ";
    std::cout << std::endl;
  }
}

void TestPriorityQueue() {
  using namespace ezstl;
  {
    int a[9] = {0, 1, 2, 3, 4, 8, 9, 3, 5};
    Priority_queue<int> pq{a, a + 9};
    std::cout << "size = " << pq.size() << std::endl;

    for (int i = 0; i < pq.size(); i++) std::cout << pq.top() << " ";
    std::cout << std::endl;

    while (!pq.empty()) {
      std::cout << pq.top() << " ";
      pq.pop();
    }
    std::cout << std::endl;
  }
  {
    std::string a[9] = {"0", "1", "2", "3", "4", "8", "9", "3", "5"};
    Priority_queue<std::string> pq{a, a + 9};
    std::cout << "size = " << pq.size() << std::endl;
    for (int i = 0; i < pq.size(); i++) std::cout << pq.top() << " ";
    std::cout << std::endl;

    while (!pq.empty()) {
      std::cout << pq.top() << " ";
      pq.pop();
    }
    std::cout << std::endl;
  }
  {
    std::cout << "========================\n";
    int a[9] = {0, 1, 2, 3, 4, 8, 9, 3, 5};
    Priority_queue<int, ezstl::Deque<int>> pq{a, a + 9};
    std::cout << "size = " << pq.size() << std::endl;

    for (int i = 0; i < pq.size(); i++) std::cout << pq.top() << " ";
    std::cout << std::endl;

    while (!pq.empty()) {
      std::cout << pq.top() << " ";
      pq.pop();
    }
    std::cout << std::endl;
  }
}

template <typename T>
struct getkey {
  const T& operator()(const T& v) const { return v; }
};

template <typename T>
struct Equal {
  bool operator()(const T& a, const T& b) const { return a == b; }
};

void TestHashTable() {
  ezstl::Hashtable<int, int, std::hash<int>, getkey<int>, Equal<int>> table{
      50, std::hash<int>(), Equal<int>()};
  std::cout << table.size() << std::endl;
  std::cout << table.bucket_count() << std::endl;

  table.insert_unique(63);
  table.insert_unique(59);
  table.insert_unique(108);
  table.insert_unique(2);
  table.insert_unique(53);
  table.insert_unique(55);

  std::cout << table.size() << std::endl;
#if 1
  for (auto& v : table) {
    std::cout << v << " ";
  }
  std::cout << std::endl;
  /* 53 55 2 108 59 63  */
#else

  auto ite = table.begin();
  for (int i = 0; i < table.size(); ++i, ++ite) {
    std::cout << *ite << " ";
  }
  std::cout << std::endl;

  ite = table.begin();
  for (ite = table.begin(); ite != table.end(); ++ite) {
    std::cout << *ite << " ";
  }
  std::cout << std::endl;
#endif

  for (int i = 0; i < table.bucket_count(); ++i) {
    int n = table.elems_in_bucket(i);
    if (n) std::cout << "buckets[" << i << "] has " << n << " elems.\n";
  }
  /*
  buckets[0] has 1 elems.
  buckets[2] has 3 elems.
  buckets[6] has 1 elems.
  buckets[10] has 1 elems.
  */

  for (int i = 0; i <= 47; ++i) table.insert_equal(i);
  std::cout << table.size() << std::endl;
  std::cout << table.bucket_count() << std::endl;  // 发生表格重建

  for (int i = 0; i < table.bucket_count(); ++i) {
    int n = table.elems_in_bucket(i);
    if (n) std::cout << "buckets[" << i << "] has " << n << " elems.\n";
  }

  for (auto& v : table) std::cout << v << " ";
  std::cout << std::endl;
}

struct eqstr {
  bool operator()(const char* s1, const char* s2) const {
    return strcmp(s1, s2) == 0;
  }
};

void TestHashSet() {
  using Set = ezstl::Hash_set<const char*, ezstl::hash<const char*>, eqstr>;
  auto lookup = [](Set& s, const char* word) {
    Set::const_iterator it = s.find(word);
    std::cout << " " << word << ": "
              << ((it != s.end()) ? "present" : "not present") << std::endl;
  };
  Set set;
  set.insert("kiwi");
  set.insert("plum");
  set.insert("apple");
  set.insert("mango");
  set.insert("apricot");
  set.insert("banana");
  lookup(set, "mango");
  lookup(set, "apple");
  lookup(set, "durian");
  for (auto& v : set) std::cout << v << " ";
  std::cout << std::endl;
}

void TestHashMap() {
  using Hash =
      ezstl::Hash_map<const char*, int, ezstl::hash<const char*>, eqstr>;
  Hash days;
  days["january"] = 31;
  days["february"] = 28;
  days["march"] = 31;
  days["april"] = 30;
  days["may"] = 31;
  days["june"] = 30;
  days["july"] = 31;
  days["august"] = 31;
  days["september"] = 30;
  days["october"] = 31;
  days["november"] = 30;
  days["december"] = 31;

  std::cout << "january -> " << days["january"] << std::endl;
  std::cout << "february -> " << days["february"] << std::endl;
  std::cout << "march -> " << days["march"] << std::endl;
  std::cout << "april -> " << days["april"] << std::endl;
  std::cout << "may -> " << days["may"] << std::endl;
  std::cout << "june -> " << days["june"] << std::endl;
  std::cout << "july -> " << days["july"] << std::endl;
  std::cout << "august -> " << days["august"] << std::endl;
  std::cout << "september -> " << days["september"] << std::endl;
  std::cout << "october -> " << days["october"] << std::endl;
  std::cout << "november -> " << days["november"] << std::endl;
  std::cout << "december -> " << days["december"] << std::endl;
  std::cout << "===========" << std::endl;
  for (auto& v : days) std::cout << v.first << " -> " << v.second << std::endl;
}

int main() {
  // TestVector();
  // TestList();
  // TestDeque();
  // TestStack();
  // TestQueue();
  // TestHeapOption();
  // TestPriorityQueue();
  // TestHashTable();
  // TestHashSet();
  TestHashMap();
  return 0;
}
